package main

import (
	"fmt"
	"math"
)

//给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
//输入: [-2,1,-3,4,-1,2,1,-5,4],
//输出: 6
//解释: 连续子数组 [4,-1,2,1] 的和最大，为 6
func maxSubSeries1(nums []int) []int{
	dp := make([]int, len(nums))
	dp[0] = nums[0]
	for i := 1; i < len(nums); i++{
		dp[i] = int(math.Max(float64(dp[i-1] + nums[i]), float64(nums[i])))
	}
	return dp
}

func maxSubSeries(nums []int)int{
	sum := nums[0]
	n := nums[0]
	for i := 0; i < len(nums); i++{
		if n >0 {
			n += nums[i]
		}else{
			n = nums[i]
		}
		if sum < n{
			sum = n
		}
	}
	return sum
}

func main(){
	fmt.Println(maxSubSeries([]int{-2,1,-3,4,-1,2,1,-5,4}))
	fmt.Println(maxSubSeries1([]int{-2,1,-3,4,-1,2,1,-5,4}))
}
